#include <stdio.h>
#include <stdlib.h>
#include "diord.h"

/*计算阶乘*/
static int mult(int n){
	int ret, i;
	
	for(i = 1, ret = 1; i <= n; i++)
		ret *= i;

	return ret;
}

/*计算序列的字典序*/
static int value(int *order, int n){
	int i, ret = 0;

	for(i = 0; i < n; i++){
		int j, count = order[i] - 1;
		for(j = 0; j < i; j++)
			if(order[j] < order[i])
				count--;

		ret += count * mult(n-i-1);
	}
	return ret;
}

/*交换*/
static exchange(int *i, int *j){
	int tmp = *i;
	*i = *j;
	*j = tmp;
}

/*找出下一个序列*/
static int* next_ord(int *order, int n){
	int i, j;

	for(i = n-1; i > 0 ;i--)
		if(order[i] > order[i-1])
			break;
	if(i ==0)
		return NULL;

	int *ret = (int *)malloc(sizeof(int) * n);

	for(j = 0; j < n; j++)
		ret[j] = order[j];

	for(j = n-1; j > i-1; j--)
		if(ret[j] > ret[i-1])
			break;
	exchange(&(ret[i-1]), &(ret[j]));

	for(j = n-1; i < j; i++, j--)
		exchange(&(ret[i]), &(ret[j]));

	return ret;
}

/*这个没什么干的，只是调用别的函数*/
int diord (int n, int *order){
	int res_val, *res_ord;

	res_val = value (order, n);

	if((res_ord = next_ord (order, n)) == NULL)
		return NOTFOUND;
	
	diord_prin (res_val, res_ord, n);

	free(res_ord);

	return 0;
}
